package com.sheng.leetcode.year2022.month09.day02;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2022/09/05
 *
 * 687. 最长同值路径
 *
 * 给定一个二叉树的  root  ，返回  最长的路径的长度 ，这个路径中的  每个节点具有相同值  。 这条路径可以经过也可以不经过根节点。
 * 两个节点之间的路径长度  由它们之间的边数表示。
 *
 * 示例 1:
 * 输入：root = [5,4,5,1,1,5]
 * 输出：2
 *
 * 示例 2:
 * 输入：root = [1,4,5,4,4,5]
 * 输出：2
 *
 * 提示:
 *
 * 树的节点数的范围是  [0, 104]
 * -1000 <= Node.val <= 1000
 * 树的深度将不超过 1000
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/longest-univalue-path
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode0687 {

    @Test
    public void test01() {
//        TreeNode root = new TreeNode(5);
//        TreeNode left = new TreeNode(4);
//        left.left = new TreeNode(1);
//        left.right = new TreeNode(1);
//        TreeNode right = new TreeNode(5);
//        right.right = new TreeNode(5);
//        root.left = left;
//        root.right = right;

        TreeNode root = new TreeNode(1);
        TreeNode left = new TreeNode(4);
        left.left = new TreeNode(4);
        left.right = new TreeNode(4);
        TreeNode right = new TreeNode(5);
        right.right = new TreeNode(5);
        root.left = left;
        root.right = right;
        System.out.println(new Solution().longestUnivaluePath(root));
    }
}

class Solution {

    int max;
    public int longestUnivaluePath(TreeNode root) {
        max = 0;
        maxLength(root);
        return max;
    }

    public int maxLength(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // root的同值路径的长度
        int n = 0;
        // 遍历root的左结点
        int left = maxLength(root.left);
        // 遍历root的右结点
        int right = maxLength(root.right);
        // 如果root的左右结点的值和root结点的值都相等，则当前结点的路径长度为左右两个子树长度之和
        if (root.left != null && root.left.val == root.val && root.right != null && root.right.val == root.val) {
            max = Math.max(max, left + right + 2);
        }
        // 获取左子树路径长度
        if (root.left != null && root.left.val == root.val) {
            n = left + 1;
        }
        // 获取右子树路径长度，并与左子树进行比较
        if (root.right != null && root.right.val == root.val) {
            n = Math.max(n, right + 1);
        }
        // 将最大路径长度放入max中
        max = Math.max(max, n);
        // 返回root的最大路径长度
        return n;
    }
}

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
